package com.acwing.partition5;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class AC423采药 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split("\\s+");
        int total = Integer.parseInt(s[0]), n = Integer.parseInt(s[1]);
        int[][] medicines = new int[n][2];
        for (int i = 0; i < n; i++) {
            s = reader.readLine().split("\\s+");
            medicines[i][0] = Integer.parseInt(s[0]);
            medicines[i][1] = Integer.parseInt(s[1]);
        }
        writer.write(String.valueOf(dynamicProgramming(medicines, total)));
        writer.flush();
    }

    private static int dynamicProgramming(int[][] medicines, int total) {
        int n = medicines.length;
        int[] dp = new int[total + 1];
        for (int i = 0; i < n; i++) {
            for (int j = total; j >= medicines[i][0]; j--) {
                dp[j] = Math.max(dp[j], dp[j - medicines[i][0]] + medicines[i][1]);
            }
        }
        return dp[total];
    }
}
